package solution1.demo.demo9;

 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution {

//    //1.不同的二叉搜索树(hard)
//    public int numTrees(int n) {
//        //由 i 个结点组成的二叉搜素树个数
//        int[] dp = new int[n + 1];
//        dp[0] = 1;
//        dp[1] = 1;
//        for(int i = 2; i <= n; i++) {
//            //以第 j 个结点为头结点的左子树数量 * 以第 i - j 个结点为头结点的右子树数量
//            for(int j = 1; j <= i; j++) {
//                dp[i] += dp[j - 1] * dp[i - j];
//            }
//        }
//        return dp[n];
//    }
//
//    //2.排序链表(归并)
//    public ListNode sortList(ListNode head) {
//        return head == null ? head : mergeSortList(head);
//    }
//
//    private ListNode mergeSortList(ListNode start) {
//        if(start.next == null) {
//            return start;
//        }
//        //寻找中间节点
//        ListNode fast = start;
//        ListNode slow = start;
//        ListNode mid = null;
//        while(fast != null && fast.next != null) {
//            mid = slow;
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //分割
//        mid.next = null;
//        //继续分割成更小块
//        ListNode l1 = mergeSortList(start);
//        ListNode l2 = mergeSortList(slow);
//        //合并
//        return merge(l1, l2);
//    }
//
//    private ListNode merge(ListNode l1, ListNode l2) {
//        ListNode dummy = new ListNode();
//        ListNode cur = dummy;
//        while(l1 != null && l2 != null) {
//            if(l1.val < l2.val) {
//                cur.next = l1;
//                l1 = l1.next;
//            } else {
//                cur.next = l2;
//                l2 = l2.next;
//            }
//            cur = cur.next;
//        }
//        if(l1 != null) {
//            cur.next = l1;
//        }
//        if(l2 != null) {
//            cur.next = l2;
//        }
//        return dummy.next;
//    }

    //3.整数拆分(动态规划 + 数学)
    public int integerBreak(int n) {
        //拆分整数 i ,使其乘积最大化
        //dp[2] = 1*1;
        //dp[3] = 1*2;
        //dp[4] = 2*2;
        //dp[10] = 3*3*4;
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j < i - 1; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }

    //不同的二叉搜索树(动态规划)
    public int numTrees(int n) {
        //由 i 个结点组成的二叉树有几种
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    //4.归并链表
    private ListNode mergeSort(ListNode start) {
        if(start.next == null) {
            return start;
        }
        //寻找中间结点
        ListNode mid = null;
        ListNode fast = start;
        ListNode slow = start;
        while(fast != null && fast.next != null) {
            mid = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        //从中间分割
        mid.next = null;
        //继续分割成更小份
        ListNode l1 = mergeSort(start);
        ListNode l2 = mergeSort(slow);
        return merge(l1, l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 != null) {
            cur.next = l1;
        }
        if(l2 != null) {
            cur.next = l2;
        }
        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        return mergeSort(head);
    }

    //5.分割等和子集(0-1背包)
    public boolean canPartition(int[] nums) {
        //从前 i - 1 个商品中任选，装满大小为 j 的背包，最大重量为 dp[j]
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 == 1) {
            //肯定不行的
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[20001];
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

    //6.最后一块石头的重量 II(0-1背包)
    public int lastStoneWeightII(int[] stones) {
        int[] dp = new int[1501];
        int sum = 0;
        for(int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        for(int i = 0; i < stones.length; i++) {
            for(int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2*dp[target];
    }

    //7.目标和(0-1 背包 + 数学)
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if((sum + target) % 2 == 1) {
            //不满足题目要求的
            return 0;
        }
        int ans = (sum + target) / 2;
        if(ans < 0) {
            return 0;
        }
        int[] dp = new int[ans + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++) {
            for(int j = ans; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[ans];
    }

    //8.一和零(二维物品 0-1 背包)
    public int findMaxForm(String[] strs, int m, int n) {
        //从前 t 个中任选，装满容量为 m 个 0 和 n 个 1 的最大长度
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for(String str : strs) {
            //计数
            int x = 0;
            int y = 0;
            for(int i = 0; i < str.length(); i++) {
                if(str.charAt(i) == '0') {
                    x++;
                } else {
                    y++;
                }
            }
            for(int i = m; i >= x; i--) {
                for(int j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }
        return dp[m][n];
    }

    //9.组合总数 IV (完全背包)
    public int combinationSum4(int[] nums, int target) {
        //从前 i 个商品中任选，装满容量为 j 背包的组合个数
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int j = 0; j <= target; j++) { //背包
            for(int i = 0; i < nums.length; i++) {
                if(j - nums[i] >= 0) {
                    dp[j] = dp[j] + dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }

    //10.零钱兑换II (完全背包)
    public int change(int amount, int[] coins) {
        //从前 i 个商品中任选，装满容量为 j 的背包的方法数
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

}

class Main {
    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        Solution solution = new Solution();
        solution.findTargetSumWays(nums, 3);
    }
}
